To solve the problems existing in the off-line construction method of location fingerprint database for location fingerprint positioning based on Received Signal Strength Indication (RSSI), including large workload of collecting all the fingerprint information in the location, low construction efficiency of the location fingerprint database, and the limited precision of interpolation, a high efficient off-line construction method of the location fingerprint database based on the Singular Value Thresholding (SVT) Matrix Completion (MC) algorithm improved by the Backtracking Search optimization Algorithm (BSA) was proposed. Firstly, using the collected location fingerprint data of some reference nodes, a low-rank matrix completion model was established. Then the model was solved by the low rank MC algorithm based on the SVT. Finally, the complete location fingerprint database could be reconstructed in the location area. At the same time, the BSA was introduced to improve the optimization process of MC algorithm with the minimum kernel norm as the fitness function to solve the problem of the fuzzy optimal solution and the poor smoothness of the traditional MC theory, which could further improve the accuracy of the solution. The experimental results show that the average error between the location fingerprint database constructed by the proposed method and the actual collected location fingerprint database is only 2.7054 dB, and the average positioning error is only 0.0863 m, but nearly 50% of the off-line collection workload can be saved. The above results show that the proposed off-line construction method of the location fingerprint database can effectively reduce the workload of off-line collection stage while ensuring the accuracy, significantly improve the construction efficiency of location fingerprint database, and improve the practicability of fingerprint positioning method to a certain extent.